package com.sakura.动态规划;

import java.util.Arrays;

public class Code746_使用最小花费爬楼梯 {

    // 暴力递归
    public int minCostClimbingStairs1(int[] cost) {
        return Math.min(f1(cost, 0), f1(cost, 1));
    }
    public int f1(int[] cost, int i) {
        if (i > cost.length - 1) {
            return 0;
        }
        return Math.min(f1(cost, i + 1), f1(cost, i + 2)) + cost[i];
    }

    // 记忆化搜索
    public int minCostClimbingStairs2(int[] cost) {
        int[] dp = new int[cost.length + 1];
        Arrays.fill(dp, -1);
        return Math.min(f2(cost, 0, dp), f2(cost, 1, dp));
    }

    private int f2(int[] cost, int i, int[] dp) {
        if (i > cost.length - 1) {
            return 0;
        }
        if (dp[i] != -1) {
            return dp[i];
        }
        int ans = Math.min(f2(cost, i + 1, dp), f2(cost, i + 2, dp)) + cost[i];
        dp[i] = ans;
        return ans;
    }

    // 底-->顶
    public int minCostClimbingStairs3(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        dp[n] = 0;
        dp[n - 1] = cost[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            dp[i] = Math.min(dp[i + 1], dp[i + 2]) + cost[i];
        }
        return Math.min(dp[0], dp[1]);
    }
}
